import numpy as np


class SVRMethod:

    def __init__(self, toler, c, kernel_option=('linear', 0)):
        self.toler = toler
        self.c = c
        self.b = 0
        self.kernel = kernel_option
        self.error_cache = []
        self.alphas = []
        self.kernel_matrix = []
        self.train_x = []
        self.train_y = []

    def __get_kernel_value(self, x, x_i, kernel_option):
        num_samples = x.shape[0]
        kernel_value = np.mat(np.zeros((num_samples, 1)))
        if kernel_option[0] == 'linear':
            kernel_value = x * x_i.T
        elif kernel_option[0] == 'rbf':
            sigma = kernel_option[1]
            if sigma == 0:
                sigma = 1
            for j in range(num_samples):
                differ = np.abs(x_i - x[j, :])
                kernel_value[j] = np.exp(differ * differ.T/(-2*sigma**2))
        else:
            raise NameError('No such kind of kernel')
        return kernel_value

    def __get_kernel_matrix(self, x, kernel_option):
        num_samples = x.shape[0]
        kernel_matrix = np.mat(np.zeros((num_samples, num_samples)))
        for i in range(num_samples):
            kernel_matrix[:, i] = self.__get_kernel_value(x, x[i, :], kernel_option)
        return kernel_matrix

    def error_calculate(self, k):
        output_k = np.multiply(self.alphas, self.train_y).T * self.kernel_matrix[:, k] + self.b
        error_k = output_k - self.train_y[k]
        return error_k

    def update_error(self, k):
        error = self.error_calculate(k)
        if self.c > self.alphas[k] > 0:
            self.error_cache[k] = [1, error]
        else:
            self.error_cache[k] = [0, error]

    def select_alpha_j(self, i, error_i):
        candidate_alpha_list = np.nonzero(self.error_cache[:, 0].A)[0]
        max_step = 0
        j = 0
        error_j = 0

        if len(candidate_alpha_list) > 1:
            for k in candidate_alpha_list:
                if k == i:
                    continue
                error_k = self.error_calculate(k)
                if abs(error_i - error_k) > max_step:
                    max_step = abs(error_i - error_k)
                    j = k
                    error_j = error_k
        else:
            j = int(np.random.uniform(0, len(self.train_x)))
            error_j = self.error_calculate(j)
        return j, error_j

    def inner_loop(self, i):
        error_i = self.error_calculate(i)
        if (self.train_y[i] * error_i < -self.toler) and (self.alphas[i] < self.c) or \
                (self.train_y[i] * error_i > self.toler) and (self.alphas[i] > 0):
            j, error_j = self.select_alpha_j(i, error_i)
            alpha_i_old = self.alphas[i].copy()
            alpha_j_old = self.alphas[j].copy()
            if self.train_y[i] != self.train_y[j]:
                L = max(0, self.alphas[j] - self.alphas[i])
                H = min(self.c, self.c + self.alphas[j] - self.alphas[i])
            else:
                L = max(0, self.alphas[j] + self.alphas[i] - self.c)
                H = min(self.c, self.alphas[j] + self.alphas[i])
            if L == H:
                return 0

            similarity = 2 * self.kernel_matrix[i, j] - self.kernel_matrix[i, i] - self.kernel_matrix[j, j]
            if similarity >= 0:
                return 0
            self.alphas[j] = alpha_j_old - self.train_y[j] * (error_i - error_j) / similarity

            if self.alphas[j] > H:
                self.alphas[j] = H
            if self.alphas[j] < L:
                self.alphas[j] = L

            if abs(self.alphas[j] - alpha_j_old) < 0.00001:
                self.update_error(j)
                return 0
            self.alphas[i] = alpha_i_old + self.train_y[i] * self.train_y[j] * (alpha_j_old - self.alphas[j])

            b1 = self.b - error_i - self.train_y[i] * (self.alphas[i] - alpha_i_old) * self.kernel_matrix[i, i] - \
                 self.train_y[j] * (self.alphas[j] - alpha_j_old) * self.kernel_matrix[i, j]
            b2 = self.b - error_j - self.train_y[i] * (self.alphas[i] - alpha_i_old) * self.kernel_matrix[i, j] - \
                 self.train_y[j] * (self.alphas[j] - alpha_j_old) * self.kernel_matrix[j, j]
            if (0 < self.alphas[i]) and (self.alphas[i] < self.c):
                self.b = b1
            elif (0 < self.alphas[j]) and (self.alphas[j] < self.c):
                self.b = b2
            else:
                self.b = (b1 + b2) / 2

            self.update_error(j)
            self.update_error(i)
            return 1
        else:
            return 0

    def fit(self, x, y, max_iter=100):
        num_samples = x.shape[0]
        self.train_x = np.mat(x)
        self.train_y = np.mat(np.atleast_2d(y)).T
        self.alphas = np.mat(np.zeros((num_samples, 1)))
        self.error_cache = np.mat(np.zeros((num_samples, 2)))
        self.kernel_matrix = self.__get_kernel_matrix(self.train_x, self.kernel)
        entire_set = True
        alpha_pairs_changed = 0
        iter = 0
        while iter < max_iter and (entire_set is True or alpha_pairs_changed > 0):
            alpha_pairs_changed = 0
            if entire_set:
                for i in range(num_samples):
                    alpha_pairs_changed += self.inner_loop(i)
                iter += 1
            else:
                nonBoundaryList = np.nonzero((self.alphas.A > 0) * (self.alphas.A < self.c))[0]
                for i in nonBoundaryList:
                    alpha_pairs_changed += self.inner_loop(i)
                iter += 1

            if entire_set:
                entire_set = False
            elif alpha_pairs_changed == 0:
                entire_set = True

    def predict(self, test_x):
        num_samples = np.mat(test_x).shape[0]
        support_vector_index = np.nonzero((self.alphas.A > 0))[0]
        support_vectors = self.train_x[support_vector_index]
        support_vector_labels = self.train_y[support_vector_index]
        support_vector_alphas = self.alphas[support_vector_index]
        output_y = []
        for i in range(num_samples):
            kernel_value = self.__get_kernel_value(support_vectors, np.mat(test_x)[i, :], self.kernel)
            predict = kernel_value.T * np.multiply(support_vector_labels, support_vector_alphas) + self.b
            if predict >= 0:
                output_y.append(1)
            else:
                output_y.append(-1)
        return output_y

    def test(self, test_x, test_y):
        predict_y = self.predict(test_x)
        num_sample = len(test_x)
        match_count = 0
        for i in range(num_sample):
            if predict_y[i] == test_y[i]:
                match_count += 1
        accuracy = float(match_count / num_sample)
        return accuracy

    def coff(self):
        support_vectors_index = np.nonzero(self.alphas.A > 0)[0]
        w = np.mat(np.zeros((2, 1)))
        for i in support_vectors_index:
            w = w + np.multiply(self.alphas[i] * self.train_y[i], self.train_x[i, :].T)
        return w.tolist(), self.b
